package two.chapter_2.c2_4;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_1.c1_3.Collection;

import java.awt.event.ItemEvent;
import java.util.Iterator;

public class MyIndexMinPQ<Key extends Comparable<Key>> implements Collection<Integer> {
    private int N;
    private Key[] keys;
    private int []indices;
    private int [] posOfIndex;
    public MyIndexMinPQ(int max){
        keys= (Key[]) new Comparable[max+1];
        indices=new int[max+1];
        posOfIndex=new int[max+1];
        for (int i = 0; i < posOfIndex.length; i++) {
            posOfIndex[i]=-1;
        }
    }

    /**
     * 将key和index绑定
     *
     * @param index
     * @param key
     */
    public void insert(int index,Key key){
        N++;
        keys[index]=key;
        indices[N]=index;
       // posOfIndex[index]=N;
        swim(N);
    }

    private void swim(int k) {
        while (k>1 && less(k,k/2)){
            exch(k,k/2);
            k=k/2;
        }
    }


    /**
     * 删除最小的元素，并返回该元素索引
     * 步骤：
     *      1,获取最小元素的索引 由位置得到索引，第一个位置是最小的元素索引
     *      2，元素数量-1
     *      3，交换第一个和最后一个元素位置。
     *      4，交换后对第一个元素使用下沉方法
     * @return
     */
    public int delMin(){
        int minIndex=indices[1];
        N--;
        exch(1,N+1);
        keys[indices[N+1]]=null;
        indices[N+1]=0;
        sink(1);
        return minIndex;
    }

    /**
     * 下沉操作，使较小的值都在上方
     * @param k
     */
    private void sink(int k) {
        while (2*k<N ){
            int i=2*k;
            int j=2*k+1;
            int lo=i;
            if (j<N && less(j,i)){
                lo=j;
                exch(k,lo);
                k=k*2+1;
            }else {
                exch(k,lo);
                k=k*2;
            }

        }
    }

    private boolean less(int i, int j) {
        return keys[indices[i]].compareTo(keys[indices[j]])<0;
    }

    @Override
    public boolean isEmpty() {
        return N==0;
    }

    @Override
    public int size() {
        return N;
    }



    /**
     * 交换索引 即可，无需动keys
     * 同时设置posOfIndex数组
     * @param i
     * @param j
     */
    private void exch(int i,int j){
        int temp=indices[i];
        indices[i]=indices[j];
        indices[j]=temp;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new IndexIterrator();
    }

    private class IndexIterrator implements Iterator<Integer>{
        public MyIndexMinPQ<Key> copy;
        public IndexIterrator(){
            copy=new MyIndexMinPQ<>(keys.length-1);
            for (int i=1;i<=size();i++){
                copy.insert(indices[i],keys[indices[i]]);
            }
        }
        @Override
        public boolean hasNext() {
            return !copy.isEmpty();
        }

        @Override
        public Integer next() {
            int min=copy.delMin();
            //StdOut.print(min+" ");
            return min;
        }

        @Override
        public void remove() {

        }
    }
}
